GermanWikipedia - /page/entry.mu

Micron Document

<!DOCTYPE html>

<title>Kasiski-Test</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Kasiski-Test</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p>Der <b>Kasiski-Test</b> ist in der <a href="Kryptoanalyse" title="Kryptoanalyse">Kryptoanalyse</a> ein Hilfsmittel zur <a href="Entzifferung" title="Entzifferung">Entzifferung</a> von <a href="Geheimtext" title="Geheimtext">Chiffraten</a>, die mit dem <a href="Vigen%C3%A8re-Chiffre" title="Vigenère-Chiffre">Vigenère-Verfahren</a> erzeugt wurden. Mit ihm lässt sich die Länge des verwendeten <a href="Schl%C3%BCssel_(Kryptologie)" title="Schlüssel (Kryptologie)">Schlüsselwortes</a> bestimmen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

<p>Im Jahr 1854 gelang es dem Briten <a href="Charles_Babbage" title="Charles Babbage">Charles Babbage</a> (1791–1871), einen Vigenère-verschlüsselten Text zu <a href="Entzifferung" title="Entzifferung">entziffern</a>. Allerdings hielt er seine Methode geheim. 1863 veröffentlichte der preußische Infanteriemajor <a href="Friedrich_Wilhelm_Kasiski" title="Friedrich Wilhelm Kasiski">Friedrich Wilhelm Kasiski</a> (1805–1881) im Buch „Die Geheimschriften und die Dechiffrir-Kunst“ dieses Verfahren, das er unabhängig von Babbage erfand. Ihm zu Ehren wird das Verfahren als Kasiski-Test bezeichnet.

</p>

<div class="mw-heading mw-heading2"><h2 id="Allgemeine_Vorgehensweise">Allgemeine Vorgehensweise</h2></div>

<p>Gegeben sei das <a href="Kryptogramm" title="Kryptogramm">Kryptogramm</a>, ein Vigenère-verschlüsselter Text. Zuerst durchsucht man den Geheimtext nach Buchstabenfolgen der Länge 2 oder länger, die mehrmals vorkommen. Anschließend bestimmt man den Abstand zwischen je 2 gleichen Folgen, das heißt, man zählt die Buchstaben vom ersten Buchstaben der ersten Folge (einschließlich) bis zum ersten Buchstaben der zweiten Folge (ausschließlich). So verfährt man mit allen gefundenen Folgen und schreibt die Abstände auf. Man erhält eine Liste von <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahlen</a>. Diese werden nun in <a href="Primfaktoren" class="mw-redirect" title="Primfaktoren">Primfaktoren</a> zerlegt. Gleiche Teiler lassen sich somit schnell finden. Zufällig entstandene Übereinstimmungen sind dann auch leicht erkennbar, weil sie aus der Reihe fallen. Allerdings wird die genaue Schlüssellänge nicht bekannt, denn der Kasiski-Test liefert nur Vielfache der Schlüssellänge. Zur genauen Betrachtung kann dann aber der <a href="Friedman-Test_(Kryptologie)" title="Friedman-Test (Kryptologie)">Friedman-Test</a> herangezogen werden, der zusätzlich einen Hinweis darauf gibt, ob es sich um eine mono- oder polyalphabetische <a href="Verschl%C3%BCsselung" title="Verschlüsselung">Verschlüsselung</a> handelt.

</p>

<div class="mw-heading mw-heading2"><h2 id="Idee_des_Kasiski-Testes">Idee des Kasiski-Testes</h2></div>

<p>Weshalb liefert der Kasiski-Test recht zuverlässige Aussagen über die Schlüsselwortlänge?

Betrachten wir dazu die folgenden Verschlüsselungen:

</p><p>Der <a href="Klartext_(Kryptographie)" title="Klartext (Kryptographie)">Klartext</a> (1. Zeile) wird mit Schlüsselwort <i>PLUTO</i> (Länge 5) Vigenère-kodiert. Der Geheimtext steht in der 3. Zeile.

</p>

<pre>DER KLAR<b>TEXT</b> WIRD ZUM GEHEIM<b>TEXT</b>

PLU TOPL<b>UTOP</b> LUTO PLU TOPLUT<b>OPLU</b>

SPL DZPC<b>NXLI</b> HCKR OFG ZSWPCF<b>HTIN</b>

</pre>

<p>Im Klartext kommt zweimal die Zeichenfolge <i>TEXT</i> vor. Trotzdem unterscheiden sich die entsprechenden Zeichenfolgen im Geheimtext. Der Grund hierfür ist, dass <i>TEXT</i> das erste Mal mit <i>UTOP</i>, das zweite Mal jedoch mit <i>OPLU</i> kodiert wird. Dies geschieht deshalb, weil der Abstand zwischen <i>TEXT</i> und <i>TEXT</i> 17 Buchstaben beträgt. Das Schlüsselwort hat aber 5 Buchstaben, und weil 5 kein Teiler von 17 ist, werden beide Textstellen nicht mit demselben Teil des Schlüsselwortes kodiert, sodass auch nicht dieselben Buchstabenfolgen im Geheimtext zu erwarten sind.

Ändern wir nun das kleine Beispiel ein wenig um.

</p>

<pre>DER KLAR<b>TEXT</b> WERDE GEHEIM<b>TEXT</b>

PLU TOPL<b>UTOP</b> LUTOP LUTOPL<b>UTOP</b>

SPL DZPC<b>NXLI</b> HYKRT RYASXX<b>NXLI</b>

</pre>

<p>Dieses Mal wird <i>TEXT</i> zweimal mit <i>UTOP</i> verschlüsselt; deshalb stimmen auch die Folgen im Kryptogramm überein. Bestimmt man auch hier den Abstand zwischen <i>TEXT</i> und <i>TEXT</i>, kommt man auf 15, ein Vielfaches von 5, der Schlüsselwortlänge.

Zusammenfassend stellt man fest: Gleiche Buchstabenfolgen (Wörter, Silben, Wortstämme usw.) ergeben nur dann gleiche Buchstabenfolgen im Kryptogramm, wenn der Abstand zwischen ihnen ein Vielfaches der Schlüsselwortlänge ist. Oder anders gesagt: Tritt im Kryptogramm eine Buchstabenfolge zweimal auf und wurde mit ihr dasselbe Wort verschlüsselt, so ist der Abstand zwischen den beiden Folgen ein Vielfaches der Schlüsselwortlänge.

Beim Kasiski-Test wird nach gleichen Buchstabenfolgen im Kryptogramm gesucht. Man setzt nun voraus, dass sie dasselbe Wort verschlüsseln. Stimmt das, so ist der Abstand ein Vielfaches der Schlüsselwortlänge. Wurde aber nicht dasselbe Wort verschlüsselt, ist der Abstand kein Vielfaches der Schlüsselwortlänge, und die beiden Stellen im Geheimtext sind nur zufällig gleich. Natürlich erkennt man nicht sofort, ob „zufällig“ dieselbe Zeichenfolge entstanden ist, oder ob wirklich dasselbe Wort verschlüsselt wurde. Deshalb werden am Ende auch gemeinsame Faktoren gesucht, um die „unpassenden“ Abstände zu finden. Selbstverständlich passiert es vor allem bei kurzen Folgen, dass sie zweimal vorkommen, obwohl nicht dasselbe Wort verschlüsselt wurde. Das ist auch der Grund, warum man in der Regel nicht nach gleichen Folgen der Länge 2 sucht. Die Wahrscheinlichkeit, dass die Buchstabenfolgen im Klartext nicht übereinstimmen, ist einfach zu groß.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiele">Beispiele</h2></div>

<p>Es sei der folgende Vigenère-verschlüsselte Geheimtext gegeben.

</p>

<pre>SPL DZPC<b>NXLI</b> HYKRT RYASXX<b>NXLI</b>

</pre>

<p>Die Folge <i>NXLI</i> kommt im Geheimtext zweimal vor. Der Abstand zwischen diesen beiden Textstellen beträgt 15 Zeichen. 15 kann in die Primfaktoren 3 und 5 zerlegt werden. Unter der Annahme, dass es sich nicht um zufälliges Auftreten handelt, wird man sagen können, dass dasselbe Wort (bzw. Silbe, Wortanfang o. ä.) verschlüsselt wurde. Man wird hier also annehmen, dass das Schlüsselwort die Länge 3, 5 oder 15 hat.

</p><p>Selbstverständlich können bei längeren Geheimtexten genauere Aussagen über die Länge des Schlüsselwortes getroffen werden. Die Gründe hierfür sind im Wesentlichen:

Es kommen mehrere <a href="Doppler_(Kryptologie)" title="Doppler (Kryptologie)">Buchstabenfolgen doppelt</a> vor.

Eine Buchstabenfolge (besonders bei häufig vorkommenden Wörtern, z. B. Artikel, Pronomen, Konjunktionen) kommt sogar dreimal oder noch öfter im Kryptogramm vor.

</p><p>Gegeben sei der folgende Vigenère-verschlüsselte Geheimtext (verschlüsselt wurde 1.Mose, Kapitel 1, Vers 1–4 mit dem Schlüsselwort ALTESTESTAMENT, das 14 Buchstaben lang ist). Mit dem Kasiski-Test soll die Länge des Schlüsselwortes bestimmt werden.

</p>

<pre>AXTRX TRYLC TYSZO EMLAF QWEUZ HRKDP NRVWM WXRPI

JTRHN IKMYF WLQIE NNOXW OTVXB NEXRK AFYHW KXAXF

QYAWD PKKWB WLZOF XRLSN AAWUX WTURH RFWLL WWKYF

WGAXG LPCTG ZXWOX RPIYB CSMYF WIKPA DHYBC SMYFW

KGMTE EUWAD LHSLP AVHFK HMWLK

</pre>

<p>Vorgehensweise:

Suchen gleicher Textfolgen mindestens der Länge 3, diese markieren und Abstände bestimmen.

</p>

<pre>A<i><b>XTRX TR</b></i>YLC TYSZO EMLAF QWEUZ HRKDP NRVWM W<i><b>XRPI</b></i>

JTRHN IKM<b>YF W</b>LQIE NNOXW OTVXB NEXRK AFYHW KXAXF

QYAWD PKKWB WLZOF XRLSN AAWUX WTURH RFWLL WWK<i><b>YF</b></i>

<i><b>W</b></i>GAXG LPCTG ZXWO<i><b>X RPIYB CSMYF W</b></i>IKPA DH<i><b>YBC SMYFW</b></i>

KGMTE EUWAD LHSLP AVHFK HMWLK

</pre>

<pre><b>XTR</b>: Abstand 3

<b>XRPI</b>: Abstand 98

<b>YFW</b>: Abstand 70

<b>YBCSMYFW</b>: Abstand 14

</pre>

<p>Zerlegen der Abstände in Primfaktoren.

</p>

<pre> 3 = 3

98 = 2 × 7 × 7

70 = 2 × 5 × 7

14 = 2 × 7

</pre>

<div class="mw-heading mw-heading3"><h3 id="Auswertung">Auswertung</h3></div>

<p>Wie man an der Primfaktorenzerlegung erkennen kann, sind alle Abstände (außer dem ersten) Vielfache von 14. Der Abstand 3 ist vermutlich ein zufälliges Zusammentreffen.

Daraus ergeben sich die folgenden Vermutungen für die Schlüsselwortlänge: 2, 7 oder 14, und tatsächlich hat der Schlüssel ALTESTESTAMENT die Länge 14.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Albrecht_Beutelspacher" title="Albrecht Beutelspacher">Albrecht Beutelspacher</a>: <i>Kryptologie. Eine Einführung in die Wissenschaft vom Verschlüsseln, Verbergen und Verheimlichen. Ohne alle Geheimniskrämerei, aber nicht ohne hinterlistigen Schalk, dargestellt zum Nutzen und Ergötzen des allgemeinen Publikums.</i> 2. erheblich erweiterte und hoffentlich verbesserte Auflage. Vieweg, Braunschweig 1991, ISBN 3-528-18990-8.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><span class="cite">Jens Puhle: <a rel="nofollow" class="external text" href="https://www.youtube.com/watch?v=QTmxgVIjMOA"><i>Kryptanalyse – Brechen eines Vigenère-verschlüsselten Geheimtextes mit dem Kasiski-Test.</i></a> In: <i><a href="YouTube" title="YouTube">YouTube</a>-Video (8′46″).</i> 12. April 2024,<span class="Abrufdatum"> abgerufen am 25. März 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3AKasiski-Test&rft.title=Kryptanalyse%26nbsp%3B%E2%80%93+Brechen+eines+Vigen%C3%A8re-verschl%C3%BCsselten+Geheimtextes+mit+dem+Kasiski-Test&rft.description=Kryptanalyse%26nbsp%3B%E2%80%93+Brechen+eines+Vigen%C3%A8re-verschl%C3%BCsselten+Geheimtextes+mit+dem+Kasiski-Test&rft.identifier=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DQTmxgVIjMOA&rft.creator=Jens+Puhle&rft.date=2024-04-12&rft.language=de"> </span></li></ul></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-03-25" href="https://de.wikipedia.org/wiki/?title=Kasiski-Test&oldid=254517649">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>